package g

import "math"

/*
 * @lc app=leetcode.cn id=53 lang=golang
 *
 * [53] 最大子数组和

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组 是数组中的一个连续部分。

1 <= nums.length <= 105
-104 <= nums[i] <= 104
*/

// @lc code=start
func maxSubArray(nums []int) int {
	return maxSubArrayDB(nums)
}

// db[i] = max(db[i-1],nums[i])
func maxSubArrayDB(nums []int) int {
	maxSum := math.MinInt32
	if len(nums) == 0 {
		return maxSum
	}
	pre := nums[0]
	maxSum = nums[0]
	for i := 1; i < len(nums); i++ {
		pre = max([]int{pre + nums[i], nums[i]})
		maxSum = max([]int{maxSum, pre})
	}
	return maxSum
}

func maxSubArrayN(nums []int) int {
	if len(nums) == 1 { // 一个元素直接返回
		return nums[0]
	} else if min(nums) >= 0 { // 最小值<=0,求和即可
		return sum(nums)
	} else if max(nums) <= 0 { // 最大值>=0,最小值就是连续最大值
		return max(nums)
	}

	maxSum := nums[0] // 连续最大值
	subSum := nums[0] // 局部最大值
	for _, num := range nums[1:] {
		if subSum < 0 { // 如果局部求和小于0，说明前边的和对后边没有任何帮助，只会拉低分数，直接放弃
			subSum = 0
		}
		subSum += num        // 局部累加
		if subSum > maxSum { // 保证全局大于局部和
			maxSum = subSum
		}
	}
	return maxSum
}

func min(values []int) int {
	minVal := values[0]
	for i := 1; i < len(values); i++ {
		if minVal > values[i] {
			minVal = values[i]
		}
	}
	return minVal
}

func max(values []int) int {
	maxVal := values[0]
	for i := 1; i < len(values); i++ {
		if maxVal < values[i] {
			maxVal = values[i]
		}
	}
	return maxVal
}

func sum(values []int) int {
	sumVal := values[0]
	for i := 1; i < len(values); i++ {
		sumVal += values[i]
	}
	return sumVal
}

// @lc code=end
